/FONT#0=NGR25/FONT#1=BDJ25/FONT#2=BDR25X/FONT#3=SUB/FONT#4=NGR30/FONT#5=NGR40/FONT#6=SUP
␈↓␈↓↓␈↓α␈↓β␈↓∧␈↓¬␈↓ε␈↓
␈↓ ↓H

␈↓ ↓H
␈↓∧5.Tree search.␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ α_We␈αbegin␈αwith␈αa␈αgeneral␈αdepth␈αfirst␈αtree␈αsearch␈αfunction.␈αIt␈αcan␈αbe␈αused␈αto␈αsearch␈αspecific␈αtrees
␈↓ ↓Hof␈α
possibilities␈α
by␈α
defining␈α
three␈α
auxiliary␈α
functions␈α
in␈α
a␈α
way␈α
that␈α
depends␈α
on␈α
the␈α
application.␈α
We␈α
have

␈↓ ↓H
␈↓ α_␈↓↓search p ← ␈↓αif ␈↓↓lose p ␈↓αthen ␈↓LOSE ␈↓αelse if ␈↓↓ter p ␈↓αthen ␈↓↓p ␈↓αelse ␈↓↓searchlis[successors p]␈↓
␈↓ ↓H

␈↓ ↓H
where
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓searchlis u ← ␈↓α if n ␈↓↓u ␈↓αthen ␈↓LOSE ␈↓αelse ␈↓↓{search ␈↓αa u}[λx.␈↓αif ␈↓↓x = ␈↓LOSE ␈↓αthen ␈↓↓searchlis ␈↓αd ␈↓↓u ␈↓αelse ␈↓↓x].␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ ↓HIn␈αthe␈αapplications,␈αwe␈αstart␈αwith␈αa␈αposition␈α␈↓↓p␈↓β0␈↓,␈αand␈αwe␈αare␈αlooking␈αfor␈αa␈αwin␈αin␈αthe␈αsuccessor␈αtree␈αof
␈↓ ↓H␈↓↓p␈↓β0␈↓.␈α∂Certain␈α∂positions␈α∂lose␈α∂and␈α∂there␈α∂is␈α∂no␈α∂point␈α∂looking␈α∂at␈α∂their␈α∂successors.␈α∞This␈α∞is␈α∞decided␈α∞by␈α∞the
␈↓ ↓Hpredicate␈α␈↓↓lose␈↓.␈αA␈αposition␈αis␈αa␈αwin␈αif␈αit␈αdoesn't␈αlose␈αand␈αit␈αsatisfies␈αthe␈αpredicate␈α␈↓↓ter␈↓.␈α
The␈α
successors␈α
of
␈↓ ↓Ha␈α∞position␈α∞is␈α∞given␈α∞by␈α∞the␈α∞function␈α∞␈↓↓successors␈↓,␈α∞and␈α∞the␈α∞value␈α∞of␈α∞␈↓↓search␈α∞p␈↓␈α∞is␈α∞the␈α
winning␈α
position.␈α
No
␈↓ ↓Hnon-losing␈α
position␈α
should␈α
have␈α
the␈α
name␈α
LOSE␈α
or␈α
the␈α
function␈α
won't␈α
work␈α
properly.

␈↓ α_Our␈αfirst␈αexample␈αis␈αfinding␈αa␈αpath␈αfrom␈αan␈αinitial␈αnode␈αto␈αa␈α
final␈α
node␈α
in␈α
a␈α
graph␈α
represented␈α
by
␈↓ ↓Ha␈α⊃list␈α⊃structure␈α⊃as␈α⊃described␈α⊃in␈α⊃chapter␈α⊃I.␈α⊃A␈α⊃position␈α⊃is␈α⊂a␈α⊂path␈α⊂starting␈α⊂from␈α⊂the␈α⊂initial␈α⊂node␈α⊂and
␈↓ ↓Hcontinuing␈α
to␈α
some␈α
intermediate␈α
node␈α
and␈α
is␈α
represented␈α
by␈αa␈αlist␈αof␈αits␈αnodes␈αin␈αreverse␈αorder.␈αThe
␈↓ ↓Hthree␈α
functions␈α
for␈α
this␈α
application␈α
are

␈↓ ↓H
␈↓ α_␈↓↓lose p ← ␈↓αa ␈↓↓p ␈↓ε ␈↓αd ␈↓↓p,
␈↓ ↓H

␈↓ ↓H
␈↓ α_ter p ← [␈↓αa ␈↓↓p = final],␈↓
␈↓ ↓H

␈↓ ↓H
and
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓successors p ← mapcar[␈↓αd ␈↓↓assoc[␈↓αa ␈↓↓p,graph],λx.x.p].␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ α_Another␈αexample␈αis␈α
the␈α
so-called␈α
␈↓↓Instant␈α
Insanity␈↓␈α
puzzle.␈α
There␈α
are␈α
four␈α
cubical␈α
blocks,␈α
and␈α
each
␈↓ ↓Hface␈αof␈αeach␈αblock␈αis␈αcolored␈αwith␈αone␈αof␈α
four␈α
colors.␈α
The␈α
object␈α
of␈α
the␈α
puzzle␈α
is␈α
to␈α
build␈α
a␈α
tower␈α
of␈α
all
␈↓ ↓Hfour␈αblocks␈αsuch␈αthat␈αeach␈αvertical␈αface␈αof␈αthe␈αtower␈α
involves␈α
all␈α
four␈α
colors.␈α
In␈α
order␈α
to␈α
use␈α
the␈α
above
␈↓ ↓Hdefined␈α
function␈α
␈↓↓search␈↓␈α
for␈αthis␈αpurpose,␈αwe␈αmust␈αdefine␈αthe␈αrepresentation␈αof␈αpositions␈αand␈αgive␈αthe
␈↓ ↓Hfunctions␈α␈↓↓lose,␈αter,␈α␈↓and␈α␈↓↓successors␈↓.␈αA␈αposition␈αis␈αrepresented␈αby␈αa␈αlist␈αof␈αlists␈α
-␈α
one␈α
for␈α
each␈α
face␈α
of␈α
the
␈↓ ↓Htower.␈αEach␈αsublist␈αis␈αthe␈αlist␈αof␈αcolors␈αof␈αthe␈α
faces␈α
of␈α
the␈α
blocks␈α
showing␈α
in␈α
that␈α
face.␈α
We␈α
shall␈α
assume
␈↓ ↓Hthat␈α∃the␈α∃blocks␈α∀are␈α∀described␈α∀in␈α∀the␈α∀following␈α∀longwinded␈α∀but␈α∀convenient␈α∀way.␈α∀(We'll␈α∀take␈α∀up
␈↓ ↓Hprecomputing␈α
this␈α
description␈α
later.)␈α
For␈αeach␈αblock␈αthere␈αis␈αa␈αlist␈αof␈αthe␈α24␈αorientations␈αof␈αthe␈αblock
␈↓ ↓Hwhere␈αeach␈αorientation␈αis␈αdescribed␈αas␈αa␈αlist␈αof␈αthe␈αcolors␈αaround␈αthe␈αvertical␈αfaces␈αof␈αthe␈αblock␈αwhen
␈↓ ↓Hit␈α
is␈α
in␈α
that␈α
orientation.␈α
Thus␈α
the␈α
puzzle␈α
is␈α
described␈α
by␈α
a␈α
list␈α
of␈α
lists␈α
of␈α
lists␈α
which␈α
we␈α
shall␈α
call␈α
␈↓↓puzz␈↓.

␈↓ ↓H
␈↓ α_We now have
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓p␈↓β0␈↓ = (NIL NIL NIL NIL),
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓lose p ← orlis[p,λu.␈↓αa ␈↓↓u ␈↓ε ␈↓αd ␈↓↓u],
␈↓ ↓H

␈↓ ↓H
␈↓ α_ter p ← [length ␈↓αa ␈↓↓p = 4]␈↓,
␈↓ ↓H

␈↓ ↓H
and
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓successors p ← mapcar[␈↓αa ␈↓↓nth[puzz,1 + length ␈↓αa ␈↓↓p],λx.mapcar2[p,x,λyz.z.y]],␈↓
␈↓ ↓H

␈↓ ↓H
where
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓mapcar2[u,v,f] ← ␈↓↓if n ␈↓↓u ␈↓αthen ␈↓NIL ␈↓αelse f[␈↓αa ␈↓↓u,␈↓αa ␈↓↓v] . mapcar2[␈↓αd ␈↓↓u,␈↓αd ␈↓↓v,f].␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ α_Getting␈αthe␈αinitial␈αposition␈αin␈αthe␈αdesired␈αform␈αis␈αas␈αcomplicated␈αa␈αcomputation␈αas␈αthe␈αactual␈αtree
␈↓ ↓Hsearch.␈αIt␈αcan␈αbe␈αconveniently␈αdone␈α
by␈α
a␈α
sequence␈α
of␈α
assignment␈α
statements␈α
starting␈α
with␈α
a␈α
description
␈↓ ↓Hof␈α
the␈α
blocks:

␈↓ ↓H
␈↓ α_␈↓↓puzz1 ← ␈↓((G B B W R G) (G G B G W R) (G W W R B R) (G G R B W W)).
␈↓ ↓H

␈↓ ↓H
␈↓ ↓HHere␈α∞each␈α∞block␈α
is␈α
represented␈α
by␈α
a␈α
list␈α
of␈α
the␈α
colors␈α
of␈α
the␈α
faces␈α
starting␈α
with␈α
the␈α
top␈α
face,␈α
going
␈↓ ↓Haround␈α
the␈α
sides␈α
in␈α
a␈α
clockwise␈α
direction␈α
and␈α
finishing␈α
with␈α
the␈α
bottom␈α
face.

␈↓ α_We␈αneed␈αto␈αgo␈αfrom␈α
this␈α
description␈α
of␈α
the␈α
blocks␈α
to␈α
a␈α
list␈α
of␈α
the␈α
possible␈α
cycles␈α
of␈α
colors␈α
on␈α
the
␈↓ ↓Hvertical␈αfaces␈αfor␈αthe␈α24␈αorientations␈αof␈αthe␈αblock.␈αThis␈αnot␈αeasy,␈αbecause␈αthe␈αorder␈αin␈αwhich␈αwe␈αhave
␈↓ ↓Hgiven␈αthe␈αcolors␈αis␈αnot␈αinvariant␈αunder␈αrotations␈αof␈αthe␈αblock.␈αAn␈αeasy␈αway␈αout␈αis␈αto␈αstart␈αwith␈αa␈αblock
␈↓ ↓Hwhose␈αfaces␈αare␈αassigned␈αthe␈αnumbers␈α1␈αthru␈α6␈α
starting␈α
with␈α
the␈α
top,␈α
going␈α
clockwise␈α
around␈α
the␈α
sides
␈↓ ↓Hand␈αfinishing␈αwith␈αthe␈αbottom.␈αWe␈αwrite␈αdown␈αone␈αcycle␈αof␈αside␈αcolors␈αfor␈αeach␈αchoice␈αof␈αthe␈αface␈αput
␈↓ ↓Hon␈αtop␈αand␈αget␈αthe␈αlist␈αof␈αall␈α24␈αcycles␈αby␈αappending␈αthe␈αresults␈αof␈αgenerating␈αthe␈αcyclic␈αpermutations
␈↓ ↓Hof␈α
the␈α
cycles.␈α
All␈α
this␈α
is␈α
accomplished␈α
by␈α
the␈α
assignment

␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓puzz2 ← cycles[␈↓(2 3 4 5)]*␈↓↓cycles[(␈↓(2 5 4 3)]*␈↓↓cycles[(1 2 6 4)]
␈↓ ↓H
␈↓ α_          *cycles[(1 4 6 2)]*cycles[(1 3 6 5)]*cycles[(1 5 6 3)],␈↓
␈↓ ↓H

␈↓ ↓H
where the function ␈↓↓cycles␈↓ is defined by
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓cycles u ← maplist[u,λx.x*upto[u,x]]␈↓
␈↓ ↓H

␈↓ ↓H
with the auxiliary function
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓upto[u,x] ← ␈↓αif ␈↓↓x ␈↓αeq ␈↓↓u ␈↓αthen ␈↓NIL ␈↓αelse a ␈↓↓u . upto[␈↓αd ␈↓↓u,x].␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ ↓HNext␈αwe␈αcreate␈αfor␈αeach␈αblock␈αa␈αlist␈αof␈αsubstitutions␈αexpressing␈αthe␈αcolors␈αof␈αthe␈αsix␈αnumbered␈αfaces.
␈↓ ↓HWe␈α
have

␈↓ ↓H
␈↓ α_␈↓↓puzz3 ← mapcar[puzz1,λx.prup[␈↓(1 2 3 4 5 6),␈↓↓x]],␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ ↓Hand␈α
we␈α
use␈α
these␈α
substitutions␈α
to␈α
get␈α
for␈α
each␈α
block␈α
the␈α
list␈α
of␈α
24␈α
orientations␈α
of␈α
the␈α
block.␈α
Thus

␈↓ ↓H
␈↓ α_␈↓↓puzz4 ← mapcar[puzz3,λs.sublis[s,puzz3]].
␈↓ ↓H

␈↓ ↓H
␈↓ ↓Hpuzz4␈↓␈α∂has␈α∂all␈α∂24␈α∂orientations␈α∂of␈α∂the␈α∞first␈α∞block␈α∞while␈α∞for␈α∞symmetry␈α∞reasons␈α∞we␈α∞need␈α∞only␈α∞consider
␈↓ ↓Hthree␈α
as␈α
distinct,␈α
say␈α
the␈α
first,␈α
ninth,␈α
and␈α
seventeen.␈α
So␈α
we␈α
finally␈α
get

␈↓ ↓H
␈↓ α_␈↓↓puzz ← (␈↓αa ␈↓↓nth[␈↓αa ␈↓↓puzz4,1] ␈↓αa ␈↓↓nth[␈↓αa ␈↓↓puzz4,9] ␈↓αa ␈↓↓nth[␈↓αa ␈↓↓puzz4,17]) . ␈↓αd ␈↓↓puzz4.␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ ↓HThe␈α
program␈α
when␈α
compiled␈α
runs␈α
about␈α
11␈α
seconds␈α
on␈α
the␈α
PDP-10.

␈↓ α_A␈α∂more␈α∂sophisticated␈α∂representation␈α∂of␈α∂face␈α∂cycles␈α∂and␈α∂partial␈α∂towers␈α∂makes␈α∂a␈α∂factor␈α∂of␈α∂ten
␈↓ ↓Hspeedup␈αwithout␈αchanging␈αthe␈αbasic␈αsearch␈αalgorithm.␈αA␈αface␈αcycle␈αis␈αrepresented␈α
by␈α
16␈α
bits␈α
in␈α
a␈α
word
␈↓ ↓Hfour␈α∞for␈α∞each␈α
face␈α
a␈α
particular␈α
one␈α
of␈α
which␈α
being␈α
turned␈α
on␈α
tells␈α
us␈α
the␈α
color␈α
of␈α
the␈α
face.␈α
If␈α
we␈α
␈↓αor␈↓
␈↓ ↓Hthese␈αwords␈αtogether␈αfor␈αthe␈αblocks␈αin␈αa␈αpartial␈αtower␈αwe␈αget␈αa␈αword␈αwhich␈αtells␈αus␈αfor␈αeach␈αface␈αof
␈↓ ↓Hthe␈αtower␈αwhat␈αcolors␈αhave␈αbeen␈αused.␈α
A␈α
particular␈α
face␈α
cycle␈α
from␈α
the␈α
next␈α
block␈α
can␈α
be␈α
added␈α
to␈α
the
␈↓ ↓Htower␈αif␈αthe␈α␈↓αand␈↓␈αof␈αits␈αword␈αwith␈αthe␈αword␈αrepresenting␈αthe␈αtower␈αis␈αzero.␈αWe␈α
represent␈α
a␈α
position␈α
by
␈↓ ↓Ha␈αlist␈αof␈αwords␈αrepresenting␈αits␈αpartial␈αtowers␈αwith␈α0␈αas␈αthe␈αlast␈αelement␈αand␈αthe␈αhighest␈αpartial␈αtower
␈↓ ↓Has␈αthe␈αfirst␈αelement.␈αThe␈αvirtue␈αof␈αthis␈αrepresentation␈αis␈αthat␈αit␈αmakes␈αthe␈αdescription␈αof␈αthe␈αalgorithm
␈↓ ↓Hshort.␈α
The␈α
initial␈α
position␈α
is␈α
(0).␈α
The␈α
new␈α
␈↓↓puzz␈↓␈α
can␈α
be␈α
formed␈α
from␈α
the␈α
old␈α
one␈α
by␈α
the␈α
assignment

␈↓ ↓H
␈↓ α_␈↓↓puzza ← mapcar[puzz,λx.mapcar[x,zap]],␈↓
␈↓ ↓H

␈↓ ↓H
where
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓zap v ← ␈↓αif n ␈↓↓v ␈↓αthen ␈↓↓0 ␈↓αelse ␈↓↓poo ␈↓αa ␈↓↓v +16zap ␈↓αd ␈↓↓v,␈↓
␈↓ ↓H

␈↓ ↓H
and
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓poo x ← ␈↓αif ␈↓↓x=␈↓R ␈↓αthen ␈↓↓1 ␈↓αelse if ␈↓↓x=␈↓W ␈↓αthen ␈↓2 ␈↓αelse if ␈↓↓x=␈↓G ␈↓αthen ␈↓4 ␈↓αelse ␈↓8.
␈↓ ↓H

␈↓ ↓H
␈↓ ↓HNow␈α
we␈α
need␈α
the␈α
new␈α
functions␈α
␈↓↓lose,␈α
ter,␈α
␈↓and␈α
␈↓↓successors␈↓.␈α
These␈α
are

␈↓ ↓H
␈↓ α_␈↓↓lose p ← ␈↓αfalse␈↓↓,
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓ter p ← [length p = 5],␈↓
␈↓ ↓H

␈↓ ↓H
and
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓successors p ← mapchoose[␈↓αa ␈↓↓nth[puzza,length p],λx.␈↓αa ␈↓↓p ␈↓αand ␈↓↓x = 0,λx. [␈↓αa ␈↓↓p ␈↓αor ␈↓↓x] . p].␈↓
␈↓ ↓H

␈↓ ↓H
where
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓mapchoose[u,pred,fn] ← ␈↓αif n ␈↓↓u ␈↓αthen ␈↓NIL
␈↓ ↓H
␈↓ α_␈↓ αh␈↓αelse if ␈↓↓pred ␈↓αa ␈↓↓u ␈↓αthen ␈↓↓fn[␈↓αa ␈↓↓u] . mapchoose[␈↓αd ␈↓↓u,pred,fn] ␈↓α
␈↓ ↓H
␈↓ α_␈↓ αhelse ␈↓↓mapchoose[␈↓αd ␈↓↓u,pred,fn].␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ ↓H␈↓↓lose␈↓␈α∂is␈α∂trivial,␈α∂because␈α∂the␈α∂␈↓↓mapchoose␈↓␈α∂is␈α∂used␈α∂to␈α∞make␈α∞sure␈α∞that␈α∞only␈α∞non-losing␈α∞new␈α∞positions␈α∞are
␈↓ ↓Hgenerated␈α
by␈α
␈↓↓successors␈↓.␈α
This␈α
version␈α
runs␈α
in␈α
a␈α
little␈α
less␈α
than␈α
one␈α
second␈α
on␈α
the␈αPDP-10.␈αA␈αgreater
␈↓ ↓Hspeedup␈α∩can␈α∩be␈α∩made␈α∩by␈α∩the␈α⊃application␈α⊃of␈α⊃some␈α⊃mathematics.␈α⊃In␈α⊃fact,␈α⊃with␈α⊃enough␈α⊃mathematics,
␈↓ ↓Hextensive␈α
tree␈α
search␈α
is␈α
unnecessary␈α
in␈α
this␈α
problem.

␈↓ α_␈↓↓search␈↓␈αis␈αused␈αwhen␈αwe␈αwant␈α
to␈α
search␈α
a␈α
tree␈α
of␈α
possibilities␈α
for␈α
a␈α
solution␈α
to␈α
a␈α
problem.␈α
What␈α
if
␈↓ ↓Hwe␈αwant␈αto␈αfind␈αall␈αsolutions␈αto␈αa␈αproblem?␈αThis␈αcan␈αbe␈αdone␈αwith␈αa␈αfunction␈α␈↓↓allsol␈↓␈αthat␈αuses␈αthe␈αsame
␈↓ ↓H␈↓↓lose,␈α
ter,␈α
␈↓and␈α
␈↓↓successors␈↓␈α
functions␈α
as␈α
does␈α
␈↓↓search␈↓.␈α
The␈α
simplest␈α
way␈α
to␈α
write␈α
␈↓↓allsol␈↓␈α
is

␈↓ ↓H
␈↓ α_␈↓↓allsol p ← ␈↓αif ␈↓↓lose p ␈↓αthen ␈↓NIL ␈↓αelse if ␈↓↓ter p ␈↓αthen ␈↓↓(p) ␈↓αelse ␈↓↓mapapp[successors p,allsol],␈↓
␈↓ ↓H

␈↓ ↓H
where
␈↓ ↓H
␈↓ α_␈↓↓mapapp[u,fn] ← ␈↓αif n ␈↓↓u ␈↓αthen ␈↓NIL ␈↓αelse ␈↓↓fn[␈↓αa ␈↓↓u] . mappap[␈↓αd ␈↓↓u,fn].␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ ↓HThis␈α
form␈α
of␈α
the␈α
function␈α
is␈α
somewhat␈α
inefficient␈α
because␈α
of␈α
all␈α
the␈α␈↓↓append␈↓ing.␈αA␈αmore␈αefficient␈αform
␈↓ ↓Huses␈α
an␈α
auxiliary␈α
function␈α
as␈α
follows:

␈↓ ↓H
␈↓ α_␈↓↓allsol p ← allsola[p,␈↓NIL]
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓allsola[p,found] ← ␈↓αif ␈↓↓lose p ␈↓αthen ␈↓↓found ␈↓αelse if ␈↓↓ter p ␈↓αthen ␈↓↓p . found ␈↓αelse ␈↓↓allsolb[successors p,found],
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓allsolb[u,found] ← ␈↓αif n ␈↓↓u ␈↓αthen ␈↓↓found ␈↓αelse ␈↓↓allsolb[␈↓αd ␈↓↓u,allsola[␈↓αa ␈↓↓u,found]].␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ ↓HThe␈αrecursive␈αprogram␈αstructure␈αthat␈αarises␈αhere␈αis␈αcommon␈αwhen␈αa␈αlist␈αis␈αto␈αbe␈αformed␈αby␈αrecurring
␈↓ ↓Hthrough␈α
a␈α
list␈α
structure.

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H
␈↓∧6. Game trees.␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ α_The␈α∞positions␈α∞that␈α∞can␈α∞be␈α∞reached␈α
from␈α
an␈α
initial␈α
position␈α
in␈α
a␈α
game␈α
form␈α
a␈α
tree,␈α
and␈α
deciding
␈↓ ↓Hwhat␈αmove␈αto␈αmake␈αoften␈αinvolves␈αsearching␈α
this␈α
tree.␈α
However,␈α
game␈α
trees␈α
are␈α
searched␈α
in␈α
a␈α
different
␈↓ ↓Hway␈α
than␈α
the␈α
trees␈α
we␈α
have␈α
looked␈α
at,␈α
because␈α
the␈α
opposing␈αinterests␈αof␈αthe␈αplayers␈αmakes␈αit␈αnot␈αa
␈↓ ↓Hsearch␈α∂for␈α∂a␈α∂joint␈α∂line␈α∂of␈α∂play␈α∂that␈α∂will␈α∂lead␈α∂to␈α∂the␈α∂first␈α∂player␈α∞winning,␈α∞but␈α∞rather␈α∞a␈α∞search␈α∞for␈α∞a
␈↓ ↓Hstrategy␈α
that␈α
will␈α
lead␈α
to␈α
a␈α
win␈α
regardless␈α
of␈α
what␈α
the␈α
other␈α
player␈α
does.

␈↓ α_The␈αsimplest␈αsituation␈αis␈αcharacterized␈αby␈αa␈αfunction␈α␈↓↓successors␈↓␈αthat␈αgives␈αthe␈αpositions␈αthat␈αcan
␈↓ ↓Hbe␈αreached␈αin␈αone␈αmove,␈αa␈α
predicate␈α
␈↓↓ter␈↓␈α
that␈α
tells␈α
when␈α
a␈α
position␈α
is␈α
to␈α
be␈α
regarded␈α
as␈α
terminal␈α
for␈α
the
␈↓ ↓Hgiven␈αanalysis,␈αand␈αa␈α
function␈α
␈↓↓imval␈↓␈α
that␈α
gives␈α
a␈α
number␈α
approximating␈α
the␈α
value␈α
of␈α
the␈α
position␈α
to␈α
one
␈↓ ↓Hof␈αthe␈αplayers.␈αWe␈αshall␈αcall␈αthis␈αplayer␈αthe␈αmaximizing␈αplayer␈αand␈αhis␈αopponent␈αthe␈αminimizing␈αplayer.
␈↓ ↓HUsually,␈αthe␈αnumerical␈αvalues␈αarise,␈αbecause␈αthe␈αsearch␈αcannot␈αbe␈αcarried␈αout␈αto␈αthe␈αend␈αof␈αthe␈αgame,
␈↓ ↓Hand␈α
the␈α
analysis␈αstops␈αwith␈αreasonably␈αstatic␈αpositions␈αthat␈αcan␈αbe␈αevaluated␈αby␈αsome␈αrule.␈αNaturally,
␈↓ ↓Hthe␈αfunction␈α␈↓↓imval␈↓␈αis␈αchosen␈αto␈αbe␈αeasy␈αto␈αcalculate␈αand␈αto␈αcorrelate␈αwell␈αwith␈αthe␈α
probability␈α
that␈α
the
␈↓ ↓Hmaximizing␈α
player␈α
can␈α
win␈α
the␈α
position.

␈↓ α_The␈αsimplest␈αrule␈αfor␈αfinding␈αthe␈αcorrect␈αmove␈αin␈αa␈αposition␈αuses␈αauxiliary␈αfunctions␈α␈↓↓valmax␈↓␈αand
␈↓ ↓H␈↓↓valmin␈↓␈αthat␈αgive␈αa␈αvalue␈αto␈αa␈αposition␈αby␈αusing␈α␈↓↓imval␈↓␈αif␈αthe␈αposition␈αis␈αterminal␈αand␈αtaking␈αthe␈αmax␈αor
␈↓ ↓Hmin␈α
of␈α
the␈α
successor␈α
positions␈α
otherwise.

␈↓ α_For␈α
this␈α
we␈α
want␈αfunctions␈αfor␈αgetting␈αthe␈αmaximum␈αor␈αthe␈αminimum␈αof␈αa␈αfunction␈αon␈αa␈αlist,␈αand
␈↓ ↓Hthey␈α
are␈α
defined␈α
as␈α
follows:

␈↓ ↓H
␈↓ α_␈↓↓maxlis[u,f] ← ␈↓αif n ␈↓↓u ␈↓αthen ␈↓↓-∞ ␈↓αelse ␈↓↓max[f[␈↓αa ␈↓↓u],maxlis[␈↓αd ␈↓↓u,f]],␈↓
␈↓ ↓H

␈↓ ↓H
and
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓minlis[u,f] ← ␈↓αif n ␈↓↓u ␈↓αthen ␈↓↓∞ ␈↓αelse ␈↓↓min[f[␈↓αa ␈↓↓u],minlis[␈↓αd ␈↓↓u,f]].␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ ↓HIn␈αthese␈αfunctions,␈α-∞␈α
and␈α
∞␈α
represent␈α
numbers␈α
that␈α
are␈α
smaller␈α
and␈α
larger␈α
than␈α
any␈α
actual␈α
values␈α
that
␈↓ ↓Hwill␈αoccur␈αin␈αevaluating␈α␈↓↓f␈↓.␈αIf␈αthese␈αnumbers␈αare␈αnot␈αavailable,␈αthen␈αit␈αis␈α
necessary␈α
to␈α
prime␈α
the␈α
function
␈↓ ↓Hwith␈αthe␈αvalues␈αof␈α␈↓↓f␈↓␈αapplied␈αto␈αthe␈αfirst␈αelement␈αof␈αthe␈αlist,␈αand␈αthe␈αfunctions␈αare␈αmeaningless␈αfor␈αnull
␈↓ ↓Hlists.␈α∂Iterative␈α∂versions␈α∂of␈α∂the␈α∂functions␈α∂are␈α∂generally␈α∂better;␈α∂we␈α∂give␈α∂only␈α∂the␈α∂iterative␈α∞version␈α∞of
␈↓ ↓H␈↓↓maxlis␈↓,␈α
namely

␈↓ ↓H
␈↓ α_␈↓↓maxlis[u,f] ← maxlisa[u,-∞,f],␈↓
␈↓ ↓H

␈↓ ↓H
where
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓maxlisa[u,x,f] ← ␈↓↓if n ␈↓↓u ␈↓αthen ␈↓↓x ␈↓αelse ␈↓↓maxlisa[␈↓αd ␈↓↓u,max[x,f[␈↓αa ␈↓↓u]],f].␈↓
␈↓ ↓H

␈↓ ↓H
We now have
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓valmax p ← ␈↓αif ␈↓↓ter p ␈↓αthen ␈↓↓imval p ␈↓αelse␈↓↓maxlis[successors p,valmin]␈↓,
␈↓ ↓H

␈↓ ↓H
and
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓valmin p ← ␈↓αif ␈↓↓ter p ␈↓αthen ␈↓↓imval p ␈↓αelse␈↓↓minlis[successors p,valmax]␈↓.
␈↓ ↓H

␈↓ ↓H
The best move is now chosen by
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓movemax p ← bestmax[succesors p,valmin],␈↓
␈↓ ↓H

␈↓ ↓H
or
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓movemin p ← bestmin[succesors p,valmax],␈↓
␈↓ ↓H

␈↓ ↓H
where
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓bestmax[u,f] ← bestmaxa[␈↓αd ␈↓↓u,␈↓αa ␈↓↓u,f[␈↓αa ␈↓↓u],f],
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓bestmaxa[u,sofar,valsofar,f] ← ␈↓αif n ␈↓↓u ␈↓αthen ␈↓↓sofar
␈↓ ↓H
␈↓ α_␈↓ αh␈↓αelse if ␈↓↓f[␈↓αa ␈↓↓u] ≤ bestsofar ␈↓αthen␈↓↓bestmaxa[␈↓αd ␈↓↓u,sofar,bestsofar,f]
␈↓ ↓H
␈↓ α_␈↓ αh␈↓αelse ␈↓↓bestmaxa[␈↓αd ␈↓↓u,␈↓αa ␈↓↓u,f[␈↓αa ␈↓↓u],f],
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓bestmin[u,f] ← bestmina[␈↓αd ␈↓↓u,␈↓αa ␈↓↓u,f[␈↓αa ␈↓↓u],f],␈↓
␈↓ ↓H

␈↓ ↓H
and
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓bestmina[u,sofar,valsofar,f] ← ␈↓αif n ␈↓↓u ␈↓αthen ␈↓↓sofar
␈↓ ↓H
␈↓ α_␈↓ αh␈↓αelse if ␈↓↓f[␈↓αa ␈↓↓u] ≥ bestsofar ␈↓αthen␈↓↓bestmina[␈↓αd ␈↓↓u,sofar,bestsofar,f]
␈↓ ↓H
␈↓ α_␈↓ αh␈↓αelse ␈↓↓bestmina[␈↓αd ␈↓↓u,␈↓αa ␈↓↓u,f[␈↓αa ␈↓↓u],f].␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ α_However,␈α∂this␈α∂straight␈α∂minimax␈α∂computation␈α∂of␈α∂the␈α∞best␈α∞move␈α∞does␈α∞much␈α∞more␈α∞computation␈α∞in
␈↓ ↓Hgeneral␈α
than␈α
is␈α
usually␈α
necessary.␈α
The␈α
simplest␈α
way␈α
to␈α
see␈α
this␈α
is␈α
from␈α
the␈α
move␈α
tree␈α
of␈α
Figure␈α
2.6.

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H
␈↓ ε↔Figure 2.6

␈↓ ↓H
␈↓ ↓HWe␈α
see␈α
from␈α
this␈α
figure␈α
that␈α
it␈α
is␈α
unnecessary␈α
to␈α
examine␈α
the␈α
moves␈α
marked␈α
x,␈α
because␈αtheir␈αvalues
␈↓ ↓Hhave␈α⊂no␈α⊂effect␈α⊂on␈α⊂the␈α⊂value␈α⊂of␈α⊂the␈α⊂game␈α⊂or␈α⊂on␈α⊂the␈α⊂correct␈α⊂move␈α∂since␈α∂the␈α∂presence␈α∂of␈α∂the␈α∂9␈α∂is
␈↓ ↓Hsufficient␈αinformation␈αat␈αthis␈αpoint␈αto␈αshow␈αthat␈αthe␈αmove␈αleading␈αto␈αthe␈αvertex␈αpreceding␈αit␈αshould␈α
not
␈↓ ↓Hbe␈α
chosen␈α
by␈α
the␈α
minimizing␈α
player.

␈↓ α_The␈α∂general␈α∞situation␈α∞is␈α∞that␈α∞it␈α∞is␈α∞unnecessary␈α∞to␈α∞examine␈α∞further␈α∞moves␈α∞in␈α∞a␈α∞position␈α∞once␈α∞a
␈↓ ↓Hmove␈αis␈αfound␈αthat␈αrefutes␈αmoving␈αto␈α
the␈α
position␈α
in␈α
the␈α
first␈α
place.␈α
This␈α
idea␈α
is␈α
called␈α
the␈α
αβ-heuristic
␈↓ ↓Hand␈α
expressed␈α
in␈α
the␈α
following␈α
recursive␈α
definitions:

␈↓ ↓H
␈↓ α_␈↓↓maxval p ← maxval1[p,-∞,∞],
␈↓ ↓H

␈↓ ↓H
␈↓ α_maxval1[p,α,β] ← ␈↓αif ␈↓↓ter p ␈↓αthen ␈↓↓max[α,min[β,imval p]] ␈↓αelse ␈↓↓maxval2[successors p,α,β],
␈↓ ↓H

␈↓ ↓H
␈↓ α_maxval2[u,α,β] ← {minval1[␈↓αa ␈↓↓u,α,β]}[λw. ␈↓αif ␈↓↓w ≥ β ␈↓αthen ␈↓↓β ␈↓αelse ␈↓↓maxval2[␈↓αd ␈↓↓u,max[α,w],β]],
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓↓minval p ← minval1[p,-∞,∞],
␈↓ ↓H

␈↓ ↓H
␈↓ α_minval1[p,α,β] ← ␈↓αif ␈↓↓ter p ␈↓αthen ␈↓↓max[α,min[β,imval p]] ␈↓αelse ␈↓↓minval2[successors p,α,β],
␈↓ ↓H

␈↓ ↓H
␈↓ α_minval2[u,α,β] ← {maxval1[␈↓αa ␈↓↓u,α,β]}[λw. ␈↓αif ␈↓↓w ≤ α ␈↓αthen ␈↓↓α ␈↓αelse ␈↓↓minval2[␈↓αd ␈↓↓u,α,min[w,β]].␈↓
␈↓ ↓H

␈↓ ↓H
␈↓ α_The␈α⊃reduction␈α⊃in␈α⊃number␈α⊃of␈α⊃positions␈α⊃examined␈α⊂given␈α⊂by␈α⊂the␈α⊂αβ␈α⊂algorithm␈α⊂over␈α⊂the␈α⊂simple
␈↓ ↓Hminimax␈αalgorithm␈α
depends␈α
on␈α
the␈α
order␈α
in␈α
which␈α
the␈α
moves␈α
are␈α
examined.␈α
In␈α
the␈α
worst␈α
case,␈α
the␈α
moves
␈↓ ↓Hhappen␈α∞to␈α∞be␈α∞examined␈α∞in␈α∞inverse␈α∞order␈α∞of␈α∞merit␈α∞in␈α∞every␈α∞position␈α
on␈α
the␈α
tree,␈α
i.e.␈α
the␈α
worst␈α
move
␈↓ ↓Hfirst.␈α
In␈α
that␈α
case,␈α
there␈α
is␈α
no␈α
improvement␈α
over␈α
minimax.␈αThe␈αbest␈αcase␈αis␈αthe␈αone␈αin␈αwhich␈αthe␈αbest
␈↓ ↓Hmove␈αin␈αevery␈αposition␈αis␈αexamined␈αfirst.␈αIf␈αwe␈αlook␈α␈↓↓n␈↓␈αmoves␈αdeep␈αon␈αa␈αtree␈αthat␈αhas␈α␈↓↓k␈↓␈αsuccessors␈αto
␈↓ ↓Heach␈α∞position,␈α
then␈α
minimax␈α
looks␈α
at␈α
␈↓↓k␈↓εn␈↓␈α
positions␈α
while␈α
αβ␈α
looks␈α
at␈α
about␈α
only␈α
␈↓↓k␈↓εn/2␈↓.␈α
Thus␈α
a␈α
program
␈↓ ↓Hthat␈αlooks␈αat␈α10␈↓ε4␈↓␈αmoves␈αwith␈ααβ␈αmight␈α
have␈α
to␈α
look␈α
at␈α
10␈↓ε8␈↓␈α
with␈α
minimax.␈α
For␈α
this␈α
reason,␈α
game␈α
playing
␈↓ ↓Hprograms␈α∞using␈α∞αβ␈α∞make␈α∞a␈α∞big␈α∞effort␈α∞to␈α∞include␈α∞as␈α∞good␈α∞as␈α∞possible␈α
an␈α
ordering␈α
of␈α
moves␈α
into␈α
the
␈↓ ↓H␈↓↓successors␈↓␈αfunction.␈αWhen␈αthere␈αis␈αa␈αdeep␈α
tree␈α
search␈α
to␈α
be␈α
done,␈α
the␈α
way␈α
to␈α
make␈α
the␈α
ordering␈α
is␈α
with
␈↓ ↓Ha␈α
short␈α
look-ahead␈α
to␈α
a␈α
much␈α
smaller␈α
depth␈α
than␈α
the␈α
main␈α
search.␈α
Still␈α
shorter␈α
look-aheads␈α
are␈αused
␈↓ ↓Hdeeper␈α∞in␈α∞the␈α∞tree,␈α
and␈α
beyond␈α
a␈α
certain␈α
depth,␈α
non-look-ahead␈α
ordering␈α
methods␈α
are␈α
of␈α
decreasing
␈↓ ↓Hcomplexity.

␈↓ α_A␈α∩version␈α∩of␈α∩αβ␈α∩incorporating␈α∩optimistic␈α∩and␈α∩pessimistic␈α∩evaluations␈α∩of␈α∩positions␈α∩was␈α⊃first
␈↓ ↓Hproposed␈α∞by␈α∞McCarthy␈α∞about␈α∞1958.␈α∞Edwards␈α∞and␈α∞Hart␈α∞at␈α∞M.I.T.␈α∞about␈α∞1959␈α∞proved␈α∞that␈α∞the␈α∞present
␈↓ ↓Hversion␈α∞of␈α∞αβ␈α∞and␈α∞calculated␈α∞the␈α∞improvement␈α∞it␈α
gives␈α
over␈α
minimax.␈α
The␈α
first␈α
publication,␈α
however,
␈↓ ↓Hwas␈α∞Brudno␈α∞(1963).␈α∞It␈α∞is␈α
worth␈α
noting␈α
that␈α
αβ␈α
was␈α
not␈α
used␈α
in␈α
the␈α
early␈α
chess␈α
playing␈α
programs␈α
in
␈↓ ↓Hspite␈αof␈αthe␈αfact␈αthat␈αit␈αis␈αclearly␈αused␈αin␈αany␈αhuman␈αplay.␈αIts␈αnon-use,␈αtherefore,␈αrepresents␈αa␈αfailure
␈↓ ↓Hof␈αself-observation.␈αVery␈αlikely,␈αthere␈αare␈αa␈αnumber␈αof␈α
other␈α
algorithms␈α
used␈α
in␈α
human␈α
thought␈α
that␈α
we
␈↓ ↓Hhave␈α
not␈α
noticed␈α
an␈α
incorporated␈α
in␈α
our␈α
programs.␈α
To␈α
the␈α
extent␈α
that␈α
this␈α
is␈α
so,␈αartificial␈αintelligence
␈↓ ↓Hwill␈α
be␈α
␈↓↓a␈α
posteriori␈↓␈α
obvious␈α
even␈α
though␈α
it␈α
is␈α
␈↓↓a␈α
priori␈↓␈α
very␈α
difficult.